/**
 * [22] 括号生成
 *
 * @format
 * @lc app=leetcode.cn id=22 lang=javascript
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
// 递归剪枝
var generateParenthesis = function (n) {
    const res = []
    function dfs(countL, countR, str) {
        if (countL == n && countR == n) res.push(str)
        if (countL < n) dfs(countL + 1, countR, str + "(")
        if (countR < n && countR < countL) dfs(countL, countR + 1, str + ")")
    }
    dfs(0, 0, "")
    return res
}

/* // 分支遍历+回溯 1 <= n <= 8
var generateParenthesis = function (n) {
    // return 0 1 2 3 none L R LoR
    function whitchCanPush(countL, countR, N = n) {
        // l<n r<n r<l
        if (countL < N) {
            if (countR < countL) return 3
            else return 1
        } else {
            if (countR < N) return 2
            else return 0
        }
    }
    // 当前遍历路径
    let path = "("
    // 有效组合
    const results = []
    // 回溯节点对应 path 索引
    const branchNode = [0]
    // 剩余左右括号数量
    let [countL, countR, flag] = [1, 0, true]
    while (flag) {
        // console.log("path:", path)
        // console.log("branchNode:", branchNode)
        // console.log("results:", results)
        let top = branchNode.length - 1
        switch (whitchCanPush(countL, countR)) {
            // 左右括号用完，进行回溯
            case 0:
                results.push(path)
                let i = branchNode[top]
                while (path[i] == ")") {
                    branchNode.pop()
                    top--
                    i = branchNode[top]
                    if (path[i] == "(") break
                }
                if (top == 0) flag = false
                path = path.slice(0, i)
                countL = countR = 0
                for (char of path) char == "(" ? countL++ : countR++
                break
            // 仅可放入左括号
            case 1:
                path += "("
                countL++
                break
            // 仅可放入右括号
            case 2:
                path += ")"
                countR++
                break
            // 左右括号皆可放
            case 3:
                // 在回溯
                if (branchNode[top] == path.length) {
                    path += ")"
                    countR++
                }
                // 第一次
                else {
                    path += "("
                    countL++
                    branchNode.push(path.length - 1)
                }
                break
        }
    }
    return results
} */

/* var generateParenthesis = function (n) {
    console.log("n =", n)
    if (n == 1) return ["()"]
    else if (n == 2) return ["(())", "()()"]
    else {
        const temp = generateParenthesis(n - 1)
        console.log("n =", n)
        console.log("temp:", temp)
        const temp1 = temp.map(e => `(${e})`)
        console.log("temp1:", temp1)
        const temp2 = temp.map(e => `()${e}`)
        for (let i = 0; i < n - 2; i++) temp2.pop()
        console.log("temp2:", temp2)
        const temp3 = temp.map(e => `${e}()`)
        console.log("temp3:", temp3)
        return [...temp1, ...temp2, ...temp3]
    }
} */

// debugger
// let n = 1
// const result = generateParenthesis(n)
// console.log("result", result)
// @lc code=end
